package com.taotao.linklist;

import lombok.Getter;
import lombok.Setter;

import java.util.Objects;

/**
 * 单向有序链表
 *
 * @author youbeiwuhuan
 * @date 2020/7/8 21:43
 */
@Getter
public class SingleSortedLinkedList<T extends Comparable> {
    /**
     * 链表节点
     */
    @Getter
    @Setter
    public static class Node<T> {
        T data;
        Node<T> next;
    }


    /**
     * 链表头节点
     */
    private Node<T> head;


    public SingleSortedLinkedList() {
        this.head = new Node<>();
    }


    /**
     * 添加加元素
     *
     * @param data
     */
    public void add(T data) {
        if (null == data) {
            return;
        }

        Node<T> curNode = head;
        while (null != curNode.next) {
            if (data.compareTo(curNode.next.data) < 0) {
                break;
            }
            curNode = curNode.next;
        }

        Node<T> node = new Node<>();
        node.setData(data);

        node.next = curNode.next;
        curNode.next = node;

    }


    /**
     * 删除节点
     *
     * @param data
     */
    public void remove(T data) {
        if (null == data) {
            throw new IllegalArgumentException();
        }

        //find the target node
        Node<T> prev = head;
        Node<T> cur = prev.next;
        while (null != cur && cur.data.compareTo(data) != 0) {
            cur = cur.next;
        }

        //remove
        prev.next = cur.next;
    }


    /**
     * 合并一个链表
     */
    public void combine(SingleSortedLinkedList<T> list2) {

        if (null == list2 || null == list2.head.next) {
            throw new IllegalArgumentException();
        }


        Node<T> prev = head;
        Node<T> cur = prev.next;

        Node<T> head2 = list2.head;
        Node<T> cur2 = head2.next;

        //把list2中小的节点从list2中移除插到list
        while (null != cur && null != cur2) {
            if (cur.data.compareTo(cur2.data) > 0) {
                //1.将cur2从list2中移除
                head2.next = cur2.next;

                //2.将cur2插入list中cur之前
                cur2.next = cur;
                prev.next = cur2;

                //3. 移动prev和cur2指针
                prev = cur2;
                //4. 重置cur2指针
                cur2 = head2.next;

            } else {
                prev = cur;
                cur = cur.next;
            }
        }

        //若果list2还有剩余的话,直接将list2剩余节点接到list后面
        if (null != cur2) {
            prev.next = cur2;
        }

    }


    /**
     * 反转链表
     */
    public void reverse() {
        /**
         * 断开旧头结点，把链表中节点一个个插到旧头节点后
         */


        Node<T> nextNode = head.next;
        //断开旧头结点,这里不断开会造成翻转后尾节点自己成环
        head.next = null;

        while (null != nextNode) {
            Node<T> nextNode0 = nextNode;
            nextNode = nextNode.next;

            //把节点插到旧节点后面
            nextNode0.next = head.next;
            head.next = nextNode0;
        }

    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("head");
        Node<T> nextNode = head.next;
        while (null != nextNode) {
            sb.append(" -> ").append(nextNode.data);
            nextNode = nextNode.next;
        }

        return sb.toString();
    }
}
